(defun primep(n)
  (loop for i from 2 to (floor (sqrt n))
       do (if (zerop (mod n i)) (return nil))
       finally (return T)))

(defun pow-in (n pow)
  (loop for j = 0 then (1+ j)
     while (zerop (mod n pow))
     do (setq n (/ n pow))
     finally (return j)))

(defun list-factors(m)
  (loop for i from 2 to (floor (/  m 2))
     with facts = () 
     with n = m
     when (zerop (mod n i)) 
     do (setq facts 
	      (cons 
	       (list i (loop for j =  0 then (1+ j)
			  while (zerop (mod n i))
			  do (setq n (/ n i))
			  finally (return j))) facts))
     finally (return (if (null facts) (list (list m '1)) facts))))


(defun factors-until (n)
  (loop for i from 2 to n 
     for fac = (cons (list-factors i) fac) 
     finally (return fac)))

(defun factors(n)
  (loop for i from 1 to n
     with no = (factors-until n)
     collect (addpows no i)))

(defun addpows (l i)
  (mapcar 
   #'(lambda (x) 
       ;(print x))
       (mapcar 
	#'(lambda (y) 
	    ;(print y)) x))
	    (list (car y) (* i  (cadr y)))) x))
   l))
(defun allpows(nomax powmax)
  (loop 
     for j from 2 to powmax 
     with no = (factors-until nomax)
     with result = ()
     do (setq result (append result  (addpows no j)))
     finally (return result)))


(defun raisepows (l)
  (mapcar 
   #'(lambda (x) 
        (car (reduce ;;fixme
	;#'+ x))
	#'(lambda (y) (expt (car y) (cadr y))) x)))
  l))

(defun compres (l)
  (cond ((null l) nil)
	((null (cdr l)) l)
	((eql (car l) (cadr l))
	 (compres (rest l)))
	(t (cons (first l) (compres (rest l))))))

(print (sort  (raisepows (allpows  5 5)) #'<))


(defun list-divisors (n)
  (loop for i from 1 to (sqrt n)
        when (= (mod n i) 0)
          collect i
          and unless (= i (/ n i))
                collect (/ n i)))

(defun all-pow-under (n)
  (loop for i from 2 to n with d = nil do
	      (loop for j from 2 to n while (< (expt i j) n) 
		 do (setq d (cons (cons i j) d)))
		 finally (return d)))

(defun pow-of (a s e)
  (loop for i from s to e collect (expt a i)))

(defun duplicates-pow (n)
  (loop 
     for i in (all-pow-under n)
     for pow = (expt (car i) (cdr i))
     for j = (car i)
     with dups = 0
     do (setq dups (+ (length (intersection (pow-of j 2 n) (pow-of pow 2 n))) dups))
     finally (return (- (expt (1- n) 2) dups))))


;;this actually works better
(time
 (length 
  (delete-duplicates
    (loop 
       for i from 2 to 100 
       with result = ()
       do (setq result 
		(append 
		 (loop 
		    for j from 2 to 100 
		    collect (expt i j)) 
		 result))
       finally (return result)))))

(length
 (remove-duplicates
   (loop for i from 2 to 100
         append (loop for j from 2 to 100
   collect (expt i j)))))

(time 
 (length 
  (loop 
     for i from 2 to 100 
     with result = ()
     do (loop for j from 2 to 100 
	   for pow = (expt i j)
	   when (not (find pow result))
	   do (setq result (sort (cons pow result) #'<)))
     finally (return result))))
